'''
https://leetcode.cn/problems/all-paths-from-source-to-target/?envType=study-plan-v2&envId=graph-theory
'''

from typing import List
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        res = []
        path = []
        def dfs(u):
            if u == n - 1:
                res.append(path + [u])
                return
            path.append(u)
            for v in graph[u]:
                dfs(v)
            path.pop()
        dfs(0)
        return res